package com.test.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 构建二叉树
 */
public class BinarySortTreeDemo {
    static int maxd=0;
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 10, 12};
        Node root = null;
        for (int i = 0; i < arr.length; i++) {
            if (root == null) {
                root = new Node(arr[i]);
            } else {
                root.add(new Node(arr[i]));
            }
        }
        root.infixOrder();//递归遍历
        System.out.println("................");
        List<Integer> integers = infixOrder(root);//非递归遍历
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }

    /**
     *二叉树的深度
     **/
    public static int depth(Node node){
        if(node==null) return 0;
        int left =  depth(node.left);
        int right =  depth(node.right);
        maxd = Math.max(maxd,left+right);
        return Math.max(left,right)+1;
    }

    /**
     *递归中序遍历
     */
    static void infixOrderRecursive(Node root) {
        if (root == null) {
            return;
        }
        infixOrder(root.left);
        System.out.println(root.value);
        infixOrder(root.right);
    }

  /**
   *非递归中序遍历
   */
    static List<Integer> infixOrder(Node root) {
        List<Integer> list = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        Node top;
        Node cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.pop();
            list.add(top.value);
            cur = top.right;
        }
        return list;
    }

}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int val) {
        this.value = val;
    }

    public void add(Node node) {
        if (node == null) return;
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this.value);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}